import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

public class Text {

    public static void main(String[] args) {
        int[] array = new int[10];

        initArray(array);

        //insertSort(array);//直接插入排序
        //shellSort(array);//希尔泡排序排序
        // selectSort(array);//直接选择排序
        //Heapsort(array);//堆排序
        //bubbleSort(array);//冒冒泡排序
        //quickSort(array);//快速排序
        countSrot(array);
        System.out.println(Arrays.toString(array));
    }
    /**
     * 有序初始化
     * @param array
     */
    public static void initArray(int[] array) {
        for(int i = 0;i < array.length;i++) {
            array[i] = array.length - i;
        }
    }

    /**
     * 无序初始化
     * @param array
     */
    public static void notArray(int[] array) {
        Random random = new Random();
        for(int i = 0;i < array.length;i++) {
            array[i] = random.nextInt(1000);
        }
    }


    /**
     * 直接选择排序
     * 时间复杂度：O(n ^ 2)
     * 空间复杂度：O(1)
     * 稳定排序
     * @param array
     */
    public static void selectSort(int[] array) {
        for(int i = 0;i < array.length - 1;i++) {
            int minindex = i;
            for(int j = i; j < array.length; j++) {
                if(array[j] < array[i]) {
                    minindex = j;
                }
                swap(array,i,minindex);
            }
        }
    }

    public static void swap(int[] array , int i ,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }


    /**
     * 插入排序
     * 时间复杂度 :  O (n ^ 2)
     * 空间复杂度 ： O (1)
     * 稳定的排序算法
     */
    public static void insertSort(int[] array) {
        for(int i = 1;i < array.length;i++) {
            int tmp = array[i];
            for(int j = i - 1 ;j >= 0;j--) {
                if(array[j] > tmp) {
                    swap(array,j,j+1);
                }else {
                    swap(array,tmp,j+1);
                }
            }

        }
    }


    /**
     * 希尔排序
     * 时间复杂度 O(n^1.3 ~ n^1.5)
     * 空间复杂度 O(n)
     */
    public static void shellSort(int[] array) {
        int gap = array.length;
        while(gap > 1) {
            gap /= 2;
            shell(array,gap);
        }
    }
    public static  void shell(int[] array ,int  gap) {
        for(int i = 0;i < array.length;i++) {
            int tmp = array[i];
            for(int j = i + gap ;j < array.length ;j += gap) {
                if(array[i] > array[j]) {
                    swap(array,i,j);
                }else {
                    break;
                }
            }

        }
    }
    /**
     * 堆排序
     */

    public static void Heapsort(int[] array) {
        createHeap(array);//将数组排序成大根堆
        //到这里已排序成大根堆 ， 接下来以小到大排序
        int end = array.length - 1;
        while(end > 0) {
            swap(array,0,end);
            siftDown(array,0,end);
            end--;
        }

    }
    public static void createHeap(int[] array) {
        for(int parent = (array.length -1 -1) /2; parent >= 0 ; parent--) {
            siftDown(array,parent,array.length);
        }
    }

    private static void siftDown(int[] array, int parent,int length) {
        int child = parent * 2 + 1;
        while(child < length) {
            if(child + 1 < length && array[child+1] > array[child]) {
                child++;
            }
            //到这里child 是两个孩子最大的节点
            if(array[child] > array[parent]) {//判断孩子节点有没有父亲节点大
                swap(array,child,parent);
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }

    }


    /**
     * 冒泡排序
     *空间复杂度 O(n^2)
     * 时间复杂度 O(1)
     *  稳定排序
     */
    public static void bubbleSort(int[] array) {
        for(int i = 0; i < array.length - 1 ;i ++) {
            boolean fag = false;
            for(int j = 0; j < array.length - 1 - i; j ++) {
                if(array[j] > array[j + 1]) {
                    swap(array,j,j+1);
                    fag = true;
                }
            }
            if(!fag) {
                break;
            }
        }
    }
    /**
     * 快速排序
     */
    public static void quickSort(int[] array) {
        quick(array,0, array.length - 1);
    }
    public static void quick(int[] array,int start,int end)  {
        if(start > end) {
            return ;
        }
        int index = partition2(array,start,end);
        quick(array,start,index - 1);
        quick(array,index+1,end);
    }

    /**
     * Hoare版
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] array, int left, int right) {
        int tmp = array[left];
        int i = left;
        while(left < right) {
            while(left < right && array[right] >= tmp) {
                right--;
            }
            while(left < right && array[left] <= tmp) {
                left++;
            }
            //到这里 right 拿到的是小于 i 的， left 拿到的是大于i的
            swap(array,left,right);
        }
        swap(array,left,i);
        return left;
    }
    /**
     *挖坑法
     */
    public static int partition2(int[] array, int left, int right) {
        int tmp = array[left];
        int i = left;
        while(left < right) {
            while(left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    /**
     * 快速排序非递归版
     */
    public static void quickSortNor(int[] array) {
        int start = 0;
        int end = array.length - 1;
        Stack<Integer> stack = new Stack<>();
        int pivot = partition2(array,start,end);
        if(start < pivot - 1) {
            stack.push(start);
            stack.push(pivot - 1);
        }
        if(end > pivot + 1) {
            stack.push(pivot + 1);
            stack.push(end);
        }
        while(!stack.isEmpty()) {
            end = stack.pop();
            start = stack.pop();
            pivot = partition2(array,start,end);
            if(start < pivot - 1) {
                stack.push(start);
                stack.push(pivot - 1);
            }
            if(end > pivot + 1) {
                stack.push(pivot + 1);
                stack.push(end);
            }
        }
    }

    /**
     * 归并排序
     */
    public static void mergeSort(int[] array) {
        mergeSortFun(array,0,array.length - 1);
    }
    private static void mergeSortFun(int[] array, int left, int right) {
        if(left >= right) {
            return ;
        }
        int mid = (left + right) / 2;
        mergeSortFun(array,left,mid);
        mergeSortFun(array,mid+1,right);
        //合并
        merge(array,left,mid,right);
    }
    private static void merge(int[] array, int left, int mid, int right) {
        int s1 = left;
        int s2 = mid + 1;
        int len = right - left + 1;
        int[] tmpArr = new int[len];
        int k = 0;
        while(s1 <= mid && s2 <= right) {
            if(array[s1] <= array[s2]) {
                tmpArr[k++] = array[s1++];
            }else { //prov > left
                tmpArr[k++] = array[s2++];
            }
        }
        while(s1 <= mid) {
            tmpArr[k++] = array[s1++];
        }
        while(s2 <= right) {
            tmpArr[k++] = array[s2++];
        }
        for(int i = 0; i < tmpArr.length; i++) {
            array[i + left] = tmpArr[i];
        }
    }
    /**
     * 非递归实现归并排序
     * @param array
     */
    public static void mergeSortNor(int[] array) {
        int gap = 1;
        while(gap < array.length) {
            for(int i = 0; i < array.length;i += gap*2) {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
                if(mid >= array.length) {
                    mid = array.length - 1;
                }
                if(right >= array.length) {
                    right = array.length - 1;
                }
                merge(array,left,mid,right);
            }
            gap *= 2;
        }
    }
    /**
     * 计数排序
     */
    public static void countSrot(int[] array) {
        int minVal = array[0];
        int maxVal = array[0];
        for(int i = 0;i < array.length;i++) {
            if(array[i] < minVal) {
                minVal = array[i];
            }
            if(maxVal < array[i]) {
                maxVal = array[i];
            }
        }
        //这里确定最大 和 最小值
        int len = maxVal - minVal + 1;
        int[] count = new int[len];
        for(int i = 0; i < array.length ; i++) {
            count[array[i] - minVal]++;
        }
        int index = 0;
        for(int i = 0; i < count.length;i++) {
            while(count[i] > 0) {
                array[index] = i + minVal;
                index++;
                count[i]--;
            }
        }
    }
}
